import java.util.ArrayList;
import java.util.List;
import java.util.Random;

public class Leetcode382 {

    public static void main(String[] args) {
        ListNode listNode = new ListNode();
        List<Integer> integers = new ArrayList<>();
        integers.add(1);
        integers.add(2);
        integers.add(3);

        Solution solution = new Solution(Leetcode19.createNode(listNode, integers));
        for (int i = 0; i < 100; i++) {
            System.out.println(solution.getRandom());
        }
    }

    static class Solution {
        ListNode head;
        Random random;

        public Solution(ListNode head) {
            this.head = head;
            random = new Random();
        }

        public int getRandom() {
            int i = 1, res = 0;
            for (ListNode listNode = head; listNode != null; listNode = listNode.next) {
                if (random.nextInt(i) == 0) {
                    res = listNode.val;
                }

                ++i;
            }

            return res;
        }
    }

}
